import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class agnes 
{
	private String filePath;
	private String dataDelimiter = "\\t";
	private int ingnoreCols = 0;
	private String notAvailable = "?";
	
	private int dimension;
	private int cluster;
	private ArrayList<Cluster> clusters = new ArrayList<Cluster>();
	private List<DataPoint> dataPoints;
	
	private double eps = 0.01;
	private double[] maxAttr;
	private double[] minAttr;
	
	
	public agnes(String filePathToData) 
	{
		/* set arguments */
		this.filePath = filePathToData;
		
		/* read input */
		this.readInput();
		
		this.runAnges();
	}
	
	
	private void runAnges()
	{
		// create clusters
		for (int i = 0; i < this.dataPoints.size(); i++) 
		{
			this.clusters.add(new Cluster(i, "Name" + i));
			this.clusters.get(i).addDataPoint(this.dataPoints.get(i));
			this.dataPoints.get(i).setCluster(this.clusters.get(i));
		}
		
		this.printClusters();
		
		int hierarchicalCounter = 1;
		while (this.clusters.size() > 1) 
		{
			hierarchicalCounter++;
			
			// Deflag Cluster
			for (Cluster cluster : this.clusters) 
			{
				cluster.mergedFlag = false;
			}
			
			// Iterate over all existing clusters
			for (int z = 0; z < this.clusters.size(); z++) 
			{
				Cluster currentCluster = this.clusters.get(z);
				
				double minDistance = Double.MAX_VALUE;
				DataPoint minDataPoint = null;
				
				// Iterate over all datapoints within a cluster
				for (int i = 0; i < currentCluster.getDataPoints().size(); i++) 
				{	
					// Iterate over all existing dataPoints
					for (int j = 0; j < this.dataPoints.size(); j++)
					{
						// Point which lies within the current cluster can be ignored
						if (this.dataPoints.get(j).getCluster() == currentCluster)
							continue;
						
						// Get distance from point in current cluster to another point
						double currentDistance = 
								currentCluster.getDataPoints().get(i).getEuclideanDistanceTo(this.dataPoints.get(j));
						
						if (currentDistance < minDistance)
						{
							minDistance = currentDistance;
							minDataPoint = this.dataPoints.get(j);
						}
					}
				}
				
				// If the cluster with the nearest datapoint already merged, skip to next cluster
				if (minDataPoint.getCluster().mergedFlag)
					continue;
				
				Cluster removeCluster = minDataPoint.getCluster();
				// get all datapoint from dataPointIndex and put it into the currentCluster
				for (int i = 0; i < removeCluster.getDataPoints().size(); i++) 
				{
					DataPoint tempPoint = removeCluster.getDataPoints().get(i);
					tempPoint.setCluster(currentCluster);
					currentCluster.addDataPoint(removeCluster.getDataPoints().get(i));
				}
				
				// Remove cluster
				this.clusters.remove(removeCluster);
				
				// Cluster Flaggen
				currentCluster.mergedFlag = true;
			}
			
			System.out.println("##############################");
			System.out.println("");
			this.printClusters();
		}
		
		System.out.println(hierarchicalCounter);
	}
	
	public void printClusters() {
		for(Cluster cluster : this.clusters)
			System.out.println(cluster);
	}
	
	private void readInput() 
	{
		BufferedReader reader;
		try 
		{
			reader = new BufferedReader(new FileReader(this.getFilePath()));
			String line = reader.readLine();
			// first get the dimension of the dataPoints
			int dimension = line.split(this.getDataDelimiter()).length;
			this.dimension = dimension;	            
	        reader.close();
	        
			this.maxAttr = new double[this.getDimension()];
			this.minAttr = new double[this.getDimension()];
			for(int i = 0; i < this.getDimension(); i++) 
			{
				this.maxAttr[i] = Double.MIN_VALUE;
				this.minAttr[i] = Double.MAX_VALUE;
			}
			
	        this.dataPoints = new ArrayList<DataPoint>();
	        
	        reader = new BufferedReader(new FileReader(this.getFilePath()));
	        
	        // read all the lines and transform each to a dataPoint
	        while( (line = reader.readLine()) != null ) 
	        {
	        	String[] split = line.split(this.getDataDelimiter());
	        	if(split.length != dimension)
	        	{
	        		reader.close();
	        		throw new IOException("Data is corrupted. Abort.");
	        	}
	        	double[] tmp_attr = new double[this.getDimension()];
	        	for(int i = 0; i < split.length; i++){
	        		if(split[i].equals(this.getNotAvailable())) 
	        		{
	        			tmp_attr[i] = Double.NaN;
	        			reader.close();
	        			throw new IOException("Input is NaN. Abort.");
	        		}
	        		else
	        		{ 
	        			double val = Double.parseDouble(split[i]);
	        			tmp_attr[i] = val;
	        			if(val > this.maxAttr[i])
	        				this.maxAttr[i] = val;
	        			if(val < this.minAttr[i])
	        				this.minAttr[i] = val;
	        		}
	        	}
	        	DataPoint dataPoint = new DataPoint(tmp_attr);
	        	dataPoint.dimension = dimension;
	        	
	        	this.addDataPoint(dataPoint);
	        }
	        reader.close();
		} catch (FileNotFoundException e) 
		{
			e.printStackTrace();
		} catch (IOException e)
		{
			e.printStackTrace();
		}
	}
	
	public int getIngnoreCols() {
		return ingnoreCols;
	}

	public String getNotAvailable() {
		return notAvailable;
	}

	public String getFilePath() {
		return filePath;
	}

	public String getDataDelimiter() {
		return dataDelimiter;
	}

	public int getDimension() {
		return dimension;
	}

	public int getCluster() {
		return cluster;
	}

	public List<DataPoint> getDataPoints() {
		return dataPoints;
	}
	
	private void addDataPoint(DataPoint dataPoint) {
		this.dataPoints.add(dataPoint);
	}

	public double getEps() {
		return eps;
	}

	public double[] getMaxAttr() {
		return maxAttr;
	}

	public double[] getMinAttr() {
		return minAttr;
	}
	
	public double compareTo(kMeans kMeans) {
		
		double N1 = 0;
		double N2 = 0;
		double N3 = 0;
		double N4 = 0;
		
		if(this.getCluster() != kMeans.getCluster()) {
			System.out.println("WARNING: Cluster count different!");
			System.out.println("Abort ...");
			return Double.NaN;
		}
		
		int clusterCount = this.getCluster();
		
		// init percentage array
		int[][] p = new int[clusterCount][clusterCount];
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
				p[i][j] = 0;
			}
		}

		//map clusterings
		for (int i = 0; i < clusterCount; i++) {
			Cluster cluster1 = this.clusters.get(i);
			for (int j = 0; j < clusterCount; j++) {
				Cluster cluster2 = kMeans.getClusters()[j];
				p[i][j] = cluster1.getSamePoints(cluster2);
			}
		}
		
		Integer[] matching = new Integer[clusterCount];
		
		// print percentage array
		for (int i = 0; i < p.length; i++) {
			int max = 0;
			int index = -1;
			for (int j = 0; j < p.length; j++) {
				if(p[i][j] > max) {
					max = p[i][j];
					index = j;
				}
			}
			matching[i] = index;
		}		
						
		double n = this.getDataPoints().size();
		
		double[] tmp_i = new double[p.length];
		double[] tmp_j = new double[p.length];
		for (int i = 0; i < tmp_j.length; i++) {
			tmp_i[i] = 0;
			tmp_j[i] = 0;
		}

		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					tmp_i[i] += p[i][j];
					tmp_j[j] += p[i][j];
			}
		}		
		
		//compute N1		
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					N1 += p[i][j] * (p[i][j]-1); 
			}
		}
		N1 *= 0.5;
		
		//compute N2
		double tmp_1 = 0;
		for (int i = 0; i < p.length; i++) {
			for (int j = 0; j < p.length; j++) {
					tmp_1 += p[i][j] * p[i][j]; 
			}
		}
		double tmp_2 = 0;
		for (int i = 0; i < tmp_i.length; i++) {
			tmp_2 += tmp_i[i] * tmp_i[i];
		}
		double tmp_3 = 0;
		for (int j = 0; j < tmp_j.length; j++) {
			tmp_3 += tmp_j[j] * tmp_j[j];
		}		
		N2 = 0.5 * (n*n + tmp_1 - (tmp_2 + tmp_3));
		
		
		//compute N3
		N3 = 0.5 * (tmp_3 - tmp_1);
		
		//compute N4
		N4 = 0.5 * (tmp_2 - tmp_1);
		
//		return new double[]{N1, N2, N3, N4};
		return (N1 + N4)/(N1 + N2 + N3 + N4);
	}	
	
	
}
